{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Find Players With Zero or One Losses"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Medium"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #array #hash-table #counting #sorting"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #数组 #哈希表 #计数 #排序"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: findWinners"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #找出输掉零场或一场比赛的玩家"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>给你一个整数数组 <code>matches</code> 其中 <code>matches[i] = [winner<sub>i</sub>, loser<sub>i</sub>]</code> 表示在一场比赛中 <code>winner<sub>i</sub></code> 击败了 <code>loser<sub>i</sub></code> 。</p>\n",
    "\n",
    "<p>返回一个长度为 2 的列表<em> </em><code>answer</code> ：</p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>answer[0]</code> 是所有 <strong>没有</strong> 输掉任何比赛的玩家列表。</li>\n",
    "\t<li><code>answer[1]</code> 是所有恰好输掉 <strong>一场</strong> 比赛的玩家列表。</li>\n",
    "</ul>\n",
    "\n",
    "<p>两个列表中的值都应该按 <strong>递增</strong> 顺序返回。</p>\n",
    "\n",
    "<p><strong>注意：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li>只考虑那些参与 <strong>至少一场</strong> 比赛的玩家。</li>\n",
    "\t<li>生成的测试用例保证 <strong>不存在</strong> 两场比赛结果 <strong>相同</strong> 。</li>\n",
    "</ul>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>示例 1：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>matches = [[1,3],[2,3],[3,6],[5,6],[5,7],[4,5],[4,8],[4,9],[10,4],[10,9]]\n",
    "<strong>输出：</strong>[[1,2,10],[4,5,7,8]]\n",
    "<strong>解释：</strong>\n",
    "玩家 1、2 和 10 都没有输掉任何比赛。\n",
    "玩家 4、5、7 和 8 每个都输掉一场比赛。\n",
    "玩家 3、6 和 9 每个都输掉两场比赛。\n",
    "因此，answer[0] = [1,2,10] 和 answer[1] = [4,5,7,8] 。\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 2：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>matches = [[2,3],[1,3],[5,4],[6,4]]\n",
    "<strong>输出：</strong>[[1,2,5,6],[]]\n",
    "<strong>解释：</strong>\n",
    "玩家 1、2、5 和 6 都没有输掉任何比赛。\n",
    "玩家 3 和 4 每个都输掉两场比赛。\n",
    "因此，answer[0] = [1,2,5,6] 和 answer[1] = [] 。\n",
    "</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>1 &lt;= matches.length &lt;= 10<sup>5</sup></code></li>\n",
    "\t<li><code>matches[i].length == 2</code></li>\n",
    "\t<li><code>1 &lt;= winner<sub>i</sub>, loser<sub>i</sub> &lt;= 10<sup>5</sup></code></li>\n",
    "\t<li><code>winner<sub>i</sub> != loser<sub>i</sub></code></li>\n",
    "\t<li>所有 <code>matches[i]</code> <strong>互不相同</strong></li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [find-players-with-zero-or-one-losses](https://leetcode.cn/problems/find-players-with-zero-or-one-losses/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [find-players-with-zero-or-one-losses](https://leetcode.cn/problems/find-players-with-zero-or-one-losses/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['[[1,3],[2,3],[3,6],[5,6],[5,7],[4,5],[4,8],[4,9],[10,4],[10,9]]', '[[2,3],[1,3],[5,4],[6,4]]']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from collections import defaultdict\n",
    "from typing import DefaultDict, List, Set\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def findWinners(self, matches: List[List[int]]) -> List[List[int]]:\n",
    "        players: Set[int] = set()\n",
    "        n_lost: DefaultDict[int, int] = defaultdict(int)\n",
    "            \n",
    "        for winner, loser in matches:\n",
    "            players.add(winner)\n",
    "            players.add(loser)\n",
    "            n_lost[loser] += 1\n",
    "            \n",
    "        never_lost: List[int] = list(players - set(n_lost.keys()))\n",
    "        never_lost.sort()\n",
    "        \n",
    "        lost_one: List[int] = [player for player, n in n_lost.items() if n == 1]\n",
    "        lost_one.sort()\n",
    "        \n",
    "        return [never_lost, lost_one]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findWinners(self, matches: List[List[int]]) -> List[List[int]]:\n",
    "        lose = defaultdict(int)\n",
    "        for winner, loser in matches:\n",
    "            lose[loser] += 1\n",
    "            lose[winner] += 0\n",
    "        zero = [k for k in lose if lose[k] == 0]\n",
    "        one = [k for k in lose if lose[k] == 1]\n",
    "        return [sorted(zero), sorted(one)]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findWinners(self, matches: List[List[int]]) -> List[List[int]]:\n",
    "        m = defaultdict(int)\n",
    "        for win, lose in matches:\n",
    "            m[lose] += 1\n",
    "            m[win] += 0\n",
    "        \n",
    "        ans = [[], []]\n",
    "        for k in m:\n",
    "            if m[k] == 0:\n",
    "                ans[0].append(k)\n",
    "            if m[k] == 1:\n",
    "                ans[1].append(k)\n",
    "        \n",
    "        ans[0].sort()\n",
    "        ans[1].sort()\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findWinners(self, matches: List[List[int]]) -> List[List[int]]:\n",
    "        loses = defaultdict(int)\n",
    "        for w, l in matches:\n",
    "            loses[w] += 0\n",
    "            loses[l] += 1\n",
    "        result = [[], []]\n",
    "        for k, n in loses.items():\n",
    "            if n > 1:continue\n",
    "            result[n].append(k)\n",
    "        result[0].sort()\n",
    "        result[1].sort()\n",
    "        return result\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findWinners(self, matches: List[List[int]]) -> List[List[int]]:\n",
    "        answer0 = set()\n",
    "        answer1 = set()\n",
    "        answer2 = set()\n",
    "\n",
    "        for winner, loser in matches:\n",
    "            if loser in answer0:\n",
    "                answer0.remove(loser)\n",
    "                answer1.add(loser)\n",
    "            elif loser in answer1:\n",
    "                answer1.remove(loser)\n",
    "                answer2.add(loser)\n",
    "            elif loser not in answer2:\n",
    "                answer1.add(loser)\n",
    "            \n",
    "            if winner not in answer1 and winner not in answer2:\n",
    "                answer0.add(winner)\n",
    "            \n",
    "        return [sorted(answer0), sorted(answer1)]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findWinners(self, matches: List[List[int]]) -> List[List[int]]:\n",
    "        grad = defaultdict(int)\n",
    "        for x, y in matches:\n",
    "            grad[x] += 0\n",
    "            grad[y] += 1\n",
    "        \n",
    "        first = list()\n",
    "        second = list()\n",
    "        for k, v in grad.items():\n",
    "            if v == 0:\n",
    "                first.append(k)\n",
    "            elif v == 1:\n",
    "                second.append(k)\n",
    "        first.sort()\n",
    "        second.sort()\n",
    "        return [first, second]\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findWinners(self, matches: List[List[int]]) -> List[List[int]]:\n",
    "        win = Counter()\n",
    "        lose = Counter()\n",
    "        for a, b in matches:\n",
    "            win[a] += 1\n",
    "            lose[b] += 1\n",
    "        ans1 = []\n",
    "        ans2 = []\n",
    "        for k in win:\n",
    "            if k not in lose:\n",
    "                ans1.append(k)\n",
    "        for k, v in lose.items():\n",
    "            if v == 1:\n",
    "                ans2.append(k)\n",
    "        return [sorted(ans1), sorted(ans2)]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findWinners(self, matches: List[List[int]]) -> List[List[int]]:\n",
    "        d = dict()\n",
    "        for match in matches:\n",
    "            if match[1] in d:\n",
    "                d[match[1]] += 1\n",
    "            else:\n",
    "                d[match[1]] = 1\n",
    "        for match in matches:\n",
    "            if match[0] not in d:\n",
    "                d[match[0]] = 0\n",
    "        zero = []\n",
    "        one = []\n",
    "        for i in d.keys():\n",
    "            if d[i] == 0:\n",
    "                zero.append(i)\n",
    "            elif d[i] == 1:\n",
    "                one.append(i)\n",
    "        zero.sort()\n",
    "        one.sort()\n",
    "        return [zero, one]\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findWinners(self, matches: List[List[int]]) -> List[List[int]]:\n",
    "        win_dict = {}\n",
    "        for match in matches:\n",
    "            if match[0] not in win_dict:\n",
    "                win_dict[match[0]] = 0\n",
    "            if match[1] not in win_dict:\n",
    "                win_dict[match[1]] = 1\n",
    "            else:\n",
    "                win_dict[match[1]] += 1\n",
    "\n",
    "        answer = [[], []]\n",
    "        for key, value in win_dict.items():\n",
    "            if value == 0:\n",
    "                answer[0].append(key)\n",
    "            if value == 1:\n",
    "                answer[1].append(key)\n",
    "\n",
    "        answer[0].sort()\n",
    "        answer[1].sort()\n",
    "        return answer\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findWinners(self, matches: List[List[int]]) -> List[List[int]]:\n",
    "        zd = dict()\n",
    "        for i, j in matches:\n",
    "            if i not in zd:\n",
    "                zd[i] = 0\n",
    "            zd[j] = zd.get(j, 0)+1\n",
    "        fh = [[],[]]\n",
    "        for i, j in sorted(zd.items()):\n",
    "            if zd[i] < 2:\n",
    "                fh[zd[i]].append(i)\n",
    "        return fh\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findWinners(self, matches: List[List[int]]) -> List[List[int]]:\n",
    "        ans = [[],[]]\n",
    "        d = {}\n",
    "        for v in matches:\n",
    "            for value in v:\n",
    "                d.setdefault(value,0)\n",
    "        # 从败者组寻找answer\n",
    "        for v in matches:\n",
    "            d[v[1]] += 1\n",
    "        print(d)\n",
    "        for key,value in d.items():\n",
    "            if value == 0:\n",
    "                ans[0].append(key)\n",
    "            elif value == 1:\n",
    "                ans[1].append(key)\n",
    "        # 对列表排序\n",
    "        ans[0].sort()\n",
    "        ans[1].sort()\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findWinners(self, matches: List[List[int]]) -> List[List[int]]:\n",
    "        zd = dict()\n",
    "        for i, j in matches:\n",
    "            if i not in zd:\n",
    "                zd[i] = 0\n",
    "            zd[j] = zd.get(j, 0)+1\n",
    "        fh = [[],[]]\n",
    "        for i, j in sorted(zd.items()):\n",
    "            if zd[i] < 2:\n",
    "                fh[zd[i]].append(i)\n",
    "        return fh\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findWinners(self, matches: List[List[int]]) -> List[List[int]]:\n",
    "        pl = [[0, 0] for _ in range(100005)]\n",
    "        for x, y in matches:\n",
    "            pl[x][0] = pl[y][0] = 1\n",
    "            pl[y][1] += 1\n",
    "        ans = [[], []]\n",
    "        for i in range(len(pl)):\n",
    "            if pl[i][0]:\n",
    "                if pl[i][1] == 0:\n",
    "                    ans[0].append(i)\n",
    "                elif pl[i][1] == 1:\n",
    "                    ans[1].append(i)\n",
    "        ans[0].sort()\n",
    "        ans[1].sort()\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findWinners(self, matches: List[List[int]]) -> List[List[int]]:\n",
    "        n = 100010\n",
    "        l = [0] * n\n",
    "        st = set()\n",
    "        for x, y in matches:\n",
    "            l[y] += 1\n",
    "            st.add(y)\n",
    "            st.add(x)\n",
    "        ans0 = [i for i, x in enumerate(l) if x == 0 and i in st]\n",
    "        ans1 = [i for i, x in enumerate(l) if x == 1 and i in st]\n",
    "        return [ans0, ans1]\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findWinners(self, matches: List[List[int]]) -> List[List[int]]:\n",
    "        x1,x2=set(),defaultdict(int)\n",
    "        for i,v in matches:\n",
    "            x1.add(i)\n",
    "            x2[v]+=1\n",
    "        cnt1,cnt2=[],[]\n",
    "        for i in x1:\n",
    "            if i in x2: continue\n",
    "            else: cnt1.append(i)\n",
    "        for j in x2:\n",
    "            if x2[j]==1: cnt2.append(j)\n",
    "        return [sorted(cnt1),sorted(cnt2)]\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findWinners(self, matches: List[List[int]]) -> List[List[int]]:\n",
    "        cnt = Counter()\n",
    "        for win,los in matches:\n",
    "            if win not in cnt:\n",
    "                cnt[win] = 0\n",
    "            cnt[los] += 1\n",
    "        ans = [[],[]]\n",
    "        for key,val in cnt.items():\n",
    "            if val<2:\n",
    "                ans[val].append(key)\n",
    "        ans[0].sort()\n",
    "        ans[1].sort()\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findWinners(self, matches: List[List[int]]) -> List[List[int]]:\n",
    "        ans = [[], []]\n",
    "        d = {}\n",
    "        for winner, loser in matches:\n",
    "            if winner not in d:\n",
    "                d[winner] = 0\n",
    "            d[loser] = d.get(loser, 0) + 1\n",
    "        for player in d.keys():\n",
    "            match d[player]:\n",
    "                case 1:\n",
    "                    ans[1].append(player)\n",
    "                case 0:\n",
    "                    ans[0].append(player)\n",
    "        ans[0].sort()\n",
    "        ans[1].sort()\n",
    "        return ans\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findWinners(self, matches: List[List[int]]) -> List[List[int]]:\n",
    "        win_map = set()\n",
    "        lose_map = defaultdict(int)\n",
    "        for match in matches:\n",
    "            win_map.add(match[0])\n",
    "            lose_map[match[1]] += 1\n",
    "        win_list = []\n",
    "        for win in win_map:\n",
    "            if win not in lose_map: win_list.append(win)\n",
    "        lose_list = []\n",
    "        for k, v in lose_map.items():\n",
    "            if v == 1: lose_list.append(k)\n",
    "\n",
    "        return sorted(win_list), sorted(lose_list)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findWinners(self, matches: List[List[int]]) -> List[List[int]]:\n",
    "        cur_win=dict()\n",
    "        cur_lose=dict()\n",
    "        for i in range(len(matches)):\n",
    "            if matches[i][0] not in cur_win:\n",
    "                cur_win[matches[i][0]] = 1\n",
    "            else:\n",
    "                cur_win[matches[i][0]] += 1\n",
    "            if matches[i][1] not in cur_lose:\n",
    "                cur_lose[matches[i][1]] = 1\n",
    "            else:\n",
    "                cur_lose[matches[i][1]] += 1\n",
    "        print(cur_win)\n",
    "        print(cur_lose)\n",
    "        ans0,ans1=[],[]\n",
    "        for i in cur_win:\n",
    "            if i not in cur_lose:\n",
    "                ans0.append(i)\n",
    "        for i in cur_lose:\n",
    "            if cur_lose[i]==1:\n",
    "                ans1.append(i)\n",
    "        ans0.sort()\n",
    "        ans1.sort()\n",
    "        print([ans0,ans1])\n",
    "        return [ans0,ans1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findWinners(self, matches: List[List[int]]) -> List[List[int]]:\n",
    "        lost = Counter()\n",
    "        for a, b in matches:\n",
    "            lost[a] += 0\n",
    "            lost[b] += 1\n",
    "        win, lost_one = [], []\n",
    "        for k, v in lost.items():\n",
    "            if v == 1:\n",
    "                lost_one.append(k)\n",
    "            elif v == 0:\n",
    "                win.append(k)\n",
    "        return sorted(win), sorted(lost_one)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findWinners(self, matches: List[List[int]]) -> List[List[int]]:\n",
    "      loseTimes = dict()\n",
    "      for win, lose in matches:\n",
    "        loseTimes[win] = loseTimes.get(win, 0)\n",
    "        loseTimes[lose] = loseTimes.get(lose, 0) + 1\n",
    "      \n",
    "      ans = [[], []]\n",
    "      for key, val in loseTimes.items():\n",
    "        if val <= 1:\n",
    "          ans[val].append(key)\n",
    "      ans[0].sort()\n",
    "      ans[1].sort()\n",
    "      return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findWinners(self, matches: List[List[int]]) -> List[List[int]]:\n",
    "        rec = dict()\n",
    "        answer0, answer1 = [], []\n",
    "\n",
    "        for match in matches:\n",
    "            if match[0] not in rec:\n",
    "                rec[match[0]] = 0\n",
    "            \n",
    "            if match[1] not in rec:\n",
    "                rec[match[1]] = 1\n",
    "            else:\n",
    "                rec[match[1]] += 1\n",
    "\n",
    "        rec = sorted(rec.items())\n",
    "\n",
    "        for s in rec:\n",
    "            if s[1] == 0:\n",
    "                answer0.append(s[0])\n",
    "            elif s[1] == 1:\n",
    "                answer1.append(s[0])\n",
    "\n",
    "        return [answer0, answer1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findWinners(self, matches: List[List[int]]) -> List[List[int]]:\n",
    "        ans = [[], []]\n",
    "        d = {}\n",
    "        for winner, loser in matches:\n",
    "            if winner not in d:\n",
    "                d[winner] = 0\n",
    "            d[loser] = d.get(loser, 0) + 1\n",
    "        for player in sorted(d.keys()):\n",
    "            match d[player]:\n",
    "                case 1:\n",
    "                    ans[1].append(player)\n",
    "                case 0:\n",
    "                    ans[0].append(player)\n",
    "        return ans\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findWinners(self, matches: List[List[int]]) -> List[List[int]]:\n",
    "        win_dict = {}\n",
    "        for match in matches:\n",
    "            if match[0] not in win_dict:\n",
    "                win_dict[match[0]] = [1, 0]\n",
    "            else:\n",
    "                win_dict[match[0]][0] += 1\n",
    "            \n",
    "            if match[1] not in win_dict:\n",
    "                win_dict[match[1]] = [0, 1]\n",
    "            else:\n",
    "                win_dict[match[1]][1] += 1\n",
    "\n",
    "        answer = [[], []]\n",
    "        for key, value in win_dict.items():\n",
    "            if value[1] == 0:\n",
    "                answer[0].append(key)\n",
    "            if value[1] == 1:\n",
    "                answer[1].append(key)\n",
    "\n",
    "        answer[0].sort()\n",
    "        answer[1].sort()\n",
    "        return answer\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findWinners(self, matches: List[List[int]]) -> List[List[int]]:\n",
    "        freq = Counter()\n",
    "        for winner, loser in matches:\n",
    "            if winner not in freq:\n",
    "                freq[winner] = 0\n",
    "            freq[loser] += 1\n",
    "        \n",
    "        ans = [[], []]\n",
    "        for key, value in freq.items():\n",
    "            if value < 2:\n",
    "                ans[value].append(key)\n",
    "        \n",
    "        ans[0].sort()\n",
    "        ans[1].sort()\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findWinners(self, matches: List[List[int]]) -> List[List[int]]:\n",
    "        times = {}\n",
    "        for i in matches:\n",
    "            winner = i[0]\n",
    "            if winner not in times:\n",
    "                times[winner] = 0\n",
    "            loser = i[1]\n",
    "            if loser not in times:\n",
    "                times[loser] = 1\n",
    "            else:\n",
    "                times[loser] += 1\n",
    "        zero = []\n",
    "        one = []\n",
    "        for i in times:\n",
    "            if times[i] == 0:\n",
    "                zero.append(i)\n",
    "            elif times[i] == 1:\n",
    "                one.append(i)\n",
    "        return [sorted(zero), sorted(one)]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findWinners(self, matches: List[List[int]]) -> List[List[int]]:\n",
    "        win_dict = {}\n",
    "        for match in matches:\n",
    "            if match[0] not in win_dict:\n",
    "                win_dict[match[0]] = [1, 0]\n",
    "            else:\n",
    "                win_dict[match[0]][0] += 1\n",
    "            \n",
    "            if match[1] not in win_dict:\n",
    "                win_dict[match[1]] = [0, 1]\n",
    "            else:\n",
    "                win_dict[match[1]][1] += 1\n",
    "\n",
    "        answer = [[], []]\n",
    "        for key, value in win_dict.items():\n",
    "            if value[1] == 0:\n",
    "                answer[0].append(key)\n",
    "            if value[1] == 1:\n",
    "                answer[1].append(key)\n",
    "\n",
    "        answer[0].sort()\n",
    "        answer[1].sort()\n",
    "        return answer\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findWinners(self, matches: List[List[int]]) -> List[List[int]]:\n",
    "        dic = defaultdict(int)\n",
    "        set1 = set()\n",
    "        set2 = set()\n",
    "        for v in matches:\n",
    "            w,l = v\n",
    "            dic[l]+=1\n",
    "        for v in matches:\n",
    "            if v[0] not in dic:\n",
    "                set1.add(v[0])\n",
    "            if dic[v[1]] == 1:\n",
    "                set2.add(v[1])\n",
    "        return [sorted(set1),sorted(set2)]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findWinners(self, matches: List[List[int]]) -> List[List[int]]:\n",
    "        d = collections.defaultdict(int)\n",
    "        for win, los in matches:\n",
    "            if not d.get(win, 0):\n",
    "                d[win] = 0\n",
    "            if d.get(los, 0):\n",
    "                d[los] += 1\n",
    "            else:\n",
    "                d[los] = 1\n",
    "        \n",
    "        ans = [[],[]]\n",
    "        for team, time in d.items():\n",
    "            if time == 0:\n",
    "                ans[0].append(team)\n",
    "            elif time == 1:\n",
    "                ans[1].append(team)\n",
    "\n",
    "        ans = [sorted(i) for i in ans]\n",
    "\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findWinners(self, matches: List[List[int]]) -> List[List[int]]:\n",
    "        dic = defaultdict(int)\n",
    "        set1 = set()\n",
    "        set2 = set()\n",
    "        for v in matches:\n",
    "            w,l = v\n",
    "            dic[l]+=1\n",
    "        for v in matches:\n",
    "            if v[0] not in dic:\n",
    "                set1.add(v[0])\n",
    "            if dic[v[1]] == 1:\n",
    "                set2.add(v[1])\n",
    "        return [sorted(set1),sorted(set2)]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from typing import List\n",
    "\n",
    "class Solution:\n",
    "    def findWinners(self, matches: List[List[int]]) -> List[List[int]]:\n",
    "        wins = {}  # 记录每个玩家获胜的次数\n",
    "        losses = {}  # 记录每个玩家失利的次数\n",
    "        \n",
    "        # 更新 wins 和 losses 字典\n",
    "        for winner, loser in matches:\n",
    "            wins[winner] = wins.get(winner, 0) + 1\n",
    "            losses[loser] = losses.get(loser, 0) + 1\n",
    "        \n",
    "        # 查找没有输掉任何比赛的玩家\n",
    "        never_lost = [player for player in wins.keys() if player not in losses]\n",
    "        \n",
    "        # 查找恰好输掉一场比赛的玩家\n",
    "        lost_once = [player for player, count in losses.items() if count == 1]\n",
    "        \n",
    "        # 对结果列表进行排序\n",
    "        never_lost.sort()\n",
    "        lost_once.sort()\n",
    "        \n",
    "        return [never_lost, lost_once]\n",
    "\n",
    "# 测试代码\n",
    "sol = Solution()\n",
    "print(sol.findWinners([[1, 2], [2, 3], [3, 4]]))  # 输出应为[[1], [4]]\n",
    "print(sol.findWinners([[1, 2], [2, 1], [2, 3], [3, 4]]))  # 输出应为[[2], [1, 4]]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findWinners(self, matches: List[List[int]]) -> List[List[int]]:\n",
    "        win, lose, losemore = set(), set(), set()\n",
    "        for i,j in matches:\n",
    "            win.add(i)\n",
    "            if j in lose:\n",
    "                losemore.add(j)\n",
    "            lose.add(j)\n",
    "        return [sorted(win - lose), sorted(lose - losemore)]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findWinners(self, matches: List[List[int]]) -> List[List[int]]:\n",
    "        dic = defaultdict(int)\n",
    "        set1 = set()\n",
    "        set2 = set()\n",
    "        for v in matches:\n",
    "            dic[v[1]]+=1\n",
    "        for v in matches:\n",
    "            if v[0] not in dic:\n",
    "                set1.add(v[0])\n",
    "            if dic[v[1]] == 1:\n",
    "                set2.add(v[1])\n",
    "        return [sorted(set1),sorted(set2)]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findWinners(self, matches: List[List[int]]) -> List[List[int]]:\n",
    "        a, b = [], []\n",
    "        cnt = Counter()\n",
    "        for w, l in matches:\n",
    "            cnt[l] += 1\n",
    "        a = sorted(set(w for w, l in matches if cnt[w] == 0))\n",
    "        b = sorted(set(l for w, l in matches if cnt[l] == 1))\n",
    "\n",
    "        return [a, b]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findWinners(self, matches: List[List[int]]) -> List[List[int]]:\n",
    "        dic = defaultdict(int)\n",
    "        set1 = set()\n",
    "        set2 = set()\n",
    "        for v in matches:\n",
    "            dic[v[1]]+=1\n",
    "        for v in matches:\n",
    "            if v[0] not in dic:\n",
    "                set1.add(v[0])\n",
    "            if dic[v[1]] == 1:\n",
    "                set2.add(v[1])\n",
    "        return [sorted(set1),sorted(set2)]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findWinners(self, matches: List[List[int]]) -> List[List[int]]:\n",
    "        dic = defaultdict(int)\n",
    "        set1 = set()\n",
    "        set2 = set()\n",
    "        for v in matches:\n",
    "            dic[v[1]]+=1\n",
    "        for v in matches:\n",
    "            if v[0] not in dic:\n",
    "                set1.add(v[0])\n",
    "            if dic[v[1]] == 1:\n",
    "                set2.add(v[1])\n",
    "        return [sorted(set1),sorted(set2)]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findWinners(self, matches: List[List[int]]) -> List[List[int]]:\n",
    "        s = set()\n",
    "        ret = [0] * 100001\n",
    "        for w, l in matches:\n",
    "            s.add(w)\n",
    "            s.add(l)\n",
    "            ret[l] += 1\n",
    "        win = []\n",
    "        lose = []\n",
    "        for i in range(100001):\n",
    "            if ret[i] == 0:\n",
    "                if i in s:\n",
    "                    win.append(i)\n",
    "            elif ret[i] == 1:\n",
    "                lose.append(i)\n",
    "        return [win, lose]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findWinners(self, matches: List[List[int]]) -> List[List[int]]:\n",
    "        c = Counter(l[1] for l in matches)  # 输家计数\n",
    "        s = set(l[0] for l in matches)      # 赢家集合\n",
    "        ans = [0, 0]\n",
    "        ans[0] = sorted(s - c.keys())\n",
    "        ans[1] = sorted(k for k, v in c.items() if v == 1)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findWinners(self, matches: List[List[int]]) -> List[List[int]]:\n",
    "        winners = []\n",
    "        losers = []\n",
    "        no_lose = []\n",
    "        lose_one = []\n",
    "        cnt = defaultdict(int)\n",
    "        for win,los in matches:\n",
    "            winners.append(win)\n",
    "            losers.append(los)\n",
    "            if cnt[los]==0:\n",
    "                cnt[los] += 1\n",
    "            elif cnt[los]==1:\n",
    "                cnt[los] = -1\n",
    "            else:\n",
    "                continue\n",
    "        for key,val in cnt.items():\n",
    "            if val==1:\n",
    "                lose_one.append(key)\n",
    "        s_los = set(losers)\n",
    "        s_win = set(winners)\n",
    "        for win in s_win:\n",
    "            if win not in s_los:\n",
    "                no_lose.append(win)\n",
    "        no_lose.sort()\n",
    "        lose_one.sort()        \n",
    "        return [no_lose,lose_one]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findWinners(self, matches: List[List[int]]) -> List[List[int]]:\n",
    "        wins, loses = map(Counter, zip(*matches))\n",
    "        return [sorted([w for w in wins if w not in loses]), sorted([l for l in loses if loses[l] == 1])]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\r\n",
    "    def findWinners(self, matches: List[List[int]]) -> List[List[int]]:\r\n",
    "        winners, losers = set(), set()\r\n",
    "        record = dict()\r\n",
    "        for i, j in matches:\r\n",
    "            record.setdefault(j, 0)\r\n",
    "            record[j] += 1\r\n",
    "        for i, j in matches:\r\n",
    "            if i not in record.keys():\r\n",
    "                winners.add(i)\r\n",
    "            if record[j] == 1:\r\n",
    "                losers.add(j)\r\n",
    "        return [sorted(list(winners)), sorted(list(losers))]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findWinners(self, matches: List[List[int]]) -> List[List[int]]:\n",
    "        \n",
    "        mp = collections.defaultdict(int)\n",
    "        players = set()\n",
    "        for a, b in matches:\n",
    "            mp[b] += 1\n",
    "            players.add(a)\n",
    "            players.add(b)\n",
    "\n",
    "        \n",
    "        ans1 = []\n",
    "        ans2 = []\n",
    "\n",
    "        for p in players:\n",
    "            if p not in mp:\n",
    "                ans1.append(p)\n",
    "        \n",
    "\n",
    "        ans1.sort()\n",
    "\n",
    "        for key, val in mp.items():\n",
    "            if val == 1:\n",
    "                ans2.append(key)\n",
    "        \n",
    "        ans2.sort()\n",
    "\n",
    "        return [ans1, ans2]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findWinners(self, matches: List[List[int]]) -> List[List[int]]:\n",
    "        players = set()\n",
    "        ans = [[],[]]\n",
    "        losers = Counter([x[1] for x in matches])\n",
    "        ans[1] = [k for k, v in losers.items() if v == 1]\n",
    "        for i in matches:\n",
    "            players.add(i[0])\n",
    "            players.add(i[1])\n",
    "        ans[0] = [x for x in players if x not in losers.keys()]\n",
    "        \n",
    "        ans[0].sort()\n",
    "        ans[1].sort()\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findWinners(self, matches: List[List[int]]) -> List[List[int]]:\n",
    "        winall=[]\n",
    "        loseone=[]\n",
    "        people=set()\n",
    "        lose=dict()\n",
    "        for i in matches:\n",
    "            people.add(i[0])\n",
    "            people.add(i[1])\n",
    "            if lose.get(i[1]) is None:\n",
    "                lose[i[1]]=1\n",
    "            else:\n",
    "                lose[i[1]]+=1\n",
    "        for p in people:\n",
    "            if lose.get(p) is None:\n",
    "                winall.append(p)\n",
    "        for loser, times in lose.items():\n",
    "            if times==1:\n",
    "                loseone.append(loser)\n",
    "        winall.sort()\n",
    "        loseone.sort()\n",
    "        return [winall,loseone]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findWinners(self, matches: List[List[int]]) -> List[List[int]]:\n",
    "        s=set()\n",
    "        cnt=Counter()\n",
    "        for a,b in matches:\n",
    "            s.add(a)\n",
    "            s.add(b)\n",
    "            cnt[b]+=1\n",
    "        ans=[[],[]]\n",
    "        for x in s:\n",
    "            if cnt[x]==0:\n",
    "                ans[0].append(x)\n",
    "            elif cnt[x]==1:\n",
    "                ans[1].append(x)\n",
    "        ans[0].sort()\n",
    "        ans[1].sort()\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findWinners(self, matches: List[List[int]]) -> List[List[int]]:\n",
    "        nodes = set()\n",
    "        lose = defaultdict(int)\n",
    "        \n",
    "        for a, b in matches:\n",
    "            nodes.add(a)\n",
    "            nodes.add(b)\n",
    "            lose[b] += 1\n",
    "        nodes= sorted(nodes)\n",
    "        return [[x for x in nodes if lose[x]==0], [x for x in nodes if lose[x]==1]]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\r\n",
    "    def findWinners(self, matches: List[List[int]]) -> List[List[int]]:\r\n",
    "        winners = set()\r\n",
    "        losers = set() \r\n",
    "        for winner, loser in matches:\r\n",
    "            if winner not in losers:\r\n",
    "                winners.add(winner)\r\n",
    "            losers.add(loser)\r\n",
    "        mp = {}\r\n",
    "        for winner, loser in matches:\r\n",
    "            mp[loser] = mp.get(loser, 0) + 1\r\n",
    "        return [sorted(winners - losers), sorted([k for k, v in mp.items() if v == 1])]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findWinners(self, matches: List[List[int]]) -> List[List[int]]:\n",
    "        loseMapping = {}\n",
    "        players = set()\n",
    "        for w, l in matches:\n",
    "            players.add(w)\n",
    "            players.add(l)\n",
    "            if(l not in loseMapping):\n",
    "                loseMapping[l] = 1\n",
    "            else:\n",
    "                loseMapping[l] += 1\n",
    "        result = [[],[]]\n",
    "        result[0] = sorted(list(players - set(loseMapping.keys())))\n",
    "        for l in loseMapping:\n",
    "            if(loseMapping[l] == 1):\n",
    "                result[1].append(l)\n",
    "        result[1] = sorted(result[1])\n",
    "        return result"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findWinners(self, matches: List[List[int]]) -> List[List[int]]:\n",
    "        ans0 = set()\n",
    "        ans1 = set()\n",
    "        ans2 = set()\n",
    "        for ele in matches:\n",
    "            t = ele[1]\n",
    "            ans0.add(ele[0])\n",
    "            if t not in ans2:\n",
    "                if t in ans1:\n",
    "                    ans2.add(t)\n",
    "                    ans1.remove(t)\n",
    "                else:\n",
    "                    ans1.add(t)\n",
    "        ans0 = ans0 - ans1 & ans0 - ans2 & ans0\n",
    "        return [sorted(list(ans0)), sorted(list(ans1))]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findWinners(self, matches: List[List[int]]) -> List[List[int]]:\n",
    "        loseMapping = {}\n",
    "        players = set()\n",
    "        for w, l in matches:\n",
    "            players.add(w)\n",
    "            players.add(l)\n",
    "            if(l not in loseMapping):\n",
    "                loseMapping[l] = 1\n",
    "            else:\n",
    "                loseMapping[l] += 1\n",
    "        result = [[],[]]\n",
    "        result[0] = sorted(list(players - set(loseMapping.keys())))\n",
    "        for l in loseMapping:\n",
    "            if(loseMapping[l] == 1):\n",
    "                result[1].append(l)\n",
    "        result[1] = sorted(result[1])\n",
    "        return result"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findWinners(self, matches: List[List[int]]) -> List[List[int]]:\n",
    "        loseMapping = {}\n",
    "        players = set()\n",
    "        for w, l in matches:\n",
    "            players.add(w)\n",
    "            players.add(l)\n",
    "            if(l not in loseMapping):\n",
    "                loseMapping[l] = 1\n",
    "            else:\n",
    "                loseMapping[l] += 1\n",
    "        result = [[],[]]\n",
    "        result[0] = sorted(list(players - set(loseMapping.keys())))\n",
    "        for l in loseMapping:\n",
    "            if(loseMapping[l] == 1):\n",
    "                result[1].append(l)\n",
    "        result[1] = sorted(result[1])\n",
    "        return result"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
